'''
Created on Jul 12, 2011

@author: anupams
'''
from com.anupam.common.utils import Utils

class HeapSortArrayBased(object):
  def __init__(self, arr, size):
    self.arr = arr
    self.heapSize = size
    self.loopCount = 0

  def __largestOfThree(self, arr , nodeIndex, leftIndex, rightIndex):
    largest = None
    if not rightIndex:
      largest = leftIndex
    elif self.arr[leftIndex] > self.arr [rightIndex]:
      largest = leftIndex
    else:
      largest = rightIndex

    if self.arr[largest] > self.arr[nodeIndex]:
      temp = self.arr[nodeIndex]
      self.arr[nodeIndex] = self.arr[largest]
      self.arr[largest] = temp
      ## In case of swap with parent node , continue with recursion
      return True
    return False

  def heapify(self):
    for i in range(0, self.heapSize):
      self.__generateMaxHeap(i)
    pass

  def __generateMaxHeap(self, index):
    leftNodeIndex = 2 * (index ) + 1
    rightNodeIndex = 2 * (index) + 2

    if leftNodeIndex < self.heapSize and rightNodeIndex >= self.heapSize:
      self.__largestOfThree(arr, index, leftNodeIndex, None)
    elif rightNodeIndex < self.heapSize:
      self.__largestOfThree(arr, index, leftNodeIndex,rightNodeIndex)
    
    if index > 0:
      newIndex = index / 2
      self.__generateMaxHeap(newIndex)
    self.loopCount = self.loopCount + 1

  def __swap(self, fromIndex, toIndex):
    temp = self.arr[fromIndex]
    self.arr[fromIndex] = self.arr[toIndex]
    self.arr[toIndex] = temp
    
  def sort(self):
    while self.heapSize > 0:
      self.__swap(0, self.heapSize)
      self.heapify()
      self.heapSize = self.heapSize - 1
  
if __name__ == '__main__':
  util = Utils()
  arr = util.generateNumbers(15)
  #arr = [2, 1, 99, 92, 63, 3, 44, 26, 8, 900, 100, 11]
  #arr = [16, 4, 10, 14, 7, 9, 3, 2, 8, 1]
  print 'raw array     ' + str(arr)
  short = HeapSortArrayBased(arr, len(arr) - 1)
  short.heapify()
  print 'max heapified ' + str(arr)
  short.sort()
  print 'sorted        ' + str(arr)
